package leetcode

import "math/rand"

// https://leetcode.com/problems/insert-delete-getrandom-o1/
type RandomizedSet struct {
	elems  []int
	indexs map[int]int
}

func Constructor() RandomizedSet {
	return RandomizedSet{
		elems:  make([]int, 0),
		indexs: make(map[int]int),
	}
}

func (t *RandomizedSet) Insert(val int) bool {
	if _, ok := t.indexs[val]; ok {
		return false
	}
	t.indexs[val] = len(t.elems)
	t.elems = append(t.elems, val)
	return true
}

func (t *RandomizedSet) Remove(val int) bool {
	if _, ok := t.indexs[val]; !ok {
		return false
	}
	idx, n := t.indexs[val], len(t.elems)
	t.indexs[t.elems[n-1]] = t.indexs[val]
	t.elems[n-1], t.elems[idx] = t.elems[idx], t.elems[n-1]
	t.elems = t.elems[0 : n-1]
	delete(t.indexs, val)
	return true
}

func (t *RandomizedSet) GetRandom() int {
	idx := rand.Intn(len(t.elems))
	return t.elems[idx]
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */
